package sortAlgorithm.quickSort;

import java.util.Arrays;

/**
 * @author： pang-yun
 * @date： 2021-10-08 13:21
 * 功能目的 ：用于
 */

public class QuickSortDemo {

    public static void main(String[] args) {
        int[] arr=new int[]{6,1,2,5,9,11,4,7,8};
        sort(arr,0,8);
        System.out.println(Arrays.toString(arr));
    }


    public static void sort(int[] arr ,int low,int high){
        if (high<low)return;
        int partition = partition(arr, low, high);

        sort(arr,low,partition-1);
        sort(arr,partition+1,high);

    }

    public static int partition(int[] arr,int low, int high){
        int key=arr[low];

        int left=low+1;
        int right=high;
        int temp=0;

        while (true){
            while (arr[right]>key){
                right--;
                if (right==low)break;
            }
            while (arr[left]<key){
                left++;
                if (left==high)break;
            }
            if (left>=right){break;}else {
                temp=arr[right];
                arr[right]=arr[left];
                arr[left]=temp;
            }
        }

        temp=arr[low];
        arr[low]=arr[right];
        arr[right]=temp;
        return right;
    }

}
